use std::collections::{HashMap, HashSet};

type Coord = (i32, i32);

#[derive(Debug, Clone, Copy)]
enum Direction {
    N,
    S,
    W,
    E,
    NE,
    NW,
    SE,
    SW,
}

fn adjacent_coords(coord: &Coord) -> [Coord; 8] {
    let (x, y) = coord;
    [
        (x - 1, y - 1), (x + 0, y - 1), (x + 1, y - 1),
        (x - 1, y + 0),                 (x + 1, y + 0),
        (x - 1, y + 1), (x + 0, y + 1), (x + 1, y + 1),
    ]
}

fn next_coord(coord: &Coord, dir: Direction) -> Coord {
    let (x, y) = coord;
    match dir {
        Direction::N  => (x + 0, y - 1),
        Direction::S  => (x + 0, y + 1),
        Direction::W  => (x - 1, y + 0),
        Direction::E  => (x + 1, y + 0),
        Direction::NE => (x + 1, y - 1),
        Direction::NW => (x - 1, y - 1),
        Direction::SE => (x + 1, y + 1),
        Direction::SW => (x - 1, y + 1),
    }
}

#[derive(Debug, Clone, Copy)]
struct CheckRule {
    check_dirs: [Direction; 3],
    move_dir: Direction,
}

impl CheckRule {
    fn new(check_dirs: [Direction; 3], move_dir: Direction) -> Self {
        Self { check_dirs, move_dir }
    }
}

fn check_next_coord(coord: &Coord, check_rules: &[CheckRule], elfs: &HashSet<Coord>) -> Coord {
    if adjacent_coords(coord).into_iter().all(|c| !elfs.contains(&c)) {
        *coord
    } else {
        for check_rule in check_rules {
            if check_rule.check_dirs.iter().all(|dir| !elfs.contains(&next_coord(coord, *dir))) {
                return next_coord(coord, check_rule.move_dir);
            }
        }
        *coord
    }
}

fn parse_input() -> HashSet<Coord> {
    let mut elfs = HashSet::new();
    include_str!("../input.txt")
        .lines()
        .enumerate()
        .for_each(|(y, line)| {
            line
                .chars()
                .enumerate()
                .for_each(|(x, c)| {
                    if c == '#' {
                        elfs.insert((x as i32, y as i32));
                    }
                })
        });
    elfs
}

fn part1() {
    let elfs = parse_input();
    let check_rules: [CheckRule; 4] = [
        CheckRule::new([Direction::N, Direction::NE, Direction::NW], Direction::N),
        CheckRule::new([Direction::S, Direction::SE, Direction::SW], Direction::S),
        CheckRule::new([Direction::W, Direction::NW, Direction::SW], Direction::W),
        CheckRule::new([Direction::E, Direction::NE, Direction::SE], Direction::E),
    ];

    let mut elfs = elfs;
    for i in 0..10 {

        let cur_check_rules: Vec<CheckRule> = check_rules.iter().cycle().skip(i).take(4).copied().collect();
        
        let mut next_count = HashMap::<Coord, usize>::new();
        let mut from_to = HashMap::<Coord, Coord>::new();

        for elf_coord in elfs.iter() {
            let next_coord = check_next_coord(elf_coord, &cur_check_rules, &elfs);
            let entry = next_count.entry(next_coord).or_insert(0);
            *entry += 1;
            from_to.insert(*elf_coord, next_coord);
        }

        elfs = elfs
            .into_iter()
            .map(|elf_coord| -> Coord {
                let next_coord = from_to[&elf_coord];
                if next_count[&next_coord] == 1 {
                    next_coord
                } else {
                    elf_coord
                }
            })
            .collect();
    }

    let min_x = elfs.iter().map(|(x, _)| *x).min().unwrap();
    let max_x = elfs.iter().map(|(x, _)| *x).max().unwrap();

    let min_y = elfs.iter().map(|(_, y)| *y).min().unwrap();
    let max_y = elfs.iter().map(|(_, y)| *y).max().unwrap();

    let width = (max_x - min_x + 1) as usize;
    let heigh = (max_y - min_y + 1) as usize;

    println!("Part 1: {}", width*heigh - elfs.len());
}

fn part2() {
    let elfs = parse_input();
    let check_rules: [CheckRule; 4] = [
        CheckRule::new([Direction::N, Direction::NE, Direction::NW], Direction::N),
        CheckRule::new([Direction::S, Direction::SE, Direction::SW], Direction::S),
        CheckRule::new([Direction::W, Direction::NW, Direction::SW], Direction::W),
        CheckRule::new([Direction::E, Direction::NE, Direction::SE], Direction::E),
    ];

    let mut elfs = elfs;
    for i in 0.. {

        let cur_check_rules: Vec<CheckRule> = check_rules.iter().cycle().skip(i).take(4).copied().collect();
        
        let mut next_count = HashMap::<Coord, usize>::new();
        let mut from_to = HashMap::<Coord, Coord>::new();

        for elf_coord in elfs.iter() {
            let next_coord = check_next_coord(elf_coord, &cur_check_rules, &elfs);
            let entry = next_count.entry(next_coord).or_insert(0);
            *entry += 1;
            from_to.insert(*elf_coord, next_coord);
        }

        let mut any_move = false;
        elfs = elfs
            .into_iter()
            .map(|elf_coord| -> Coord {
                let next_coord = from_to[&elf_coord];
                if next_count[&next_coord] == 1 {
                    if next_coord != elf_coord {
                        any_move = true;
                    }
                    next_coord
                } else {
                    elf_coord
                }
            })
            .collect();

        if !any_move {
            println!("Part 2: {}", i + 1);
            return;
        }
        
    }
}

fn main() {
    part1();
    part2();
}
